package leetcode_1000;

import java.util.LinkedList;
import java.util.Queue;

public class ShortestPathInBinaryMatrix_1091 {
	public static void main(String[] args) {
		ShortestPathInBinaryMatrix_1091 test = new ShortestPathInBinaryMatrix_1091();
		//System.out.println(test.shortestPathBinaryMatrix(new int[][] {{0,1},{1,0}}));
		System.out.println(test.shortestPathBinaryMatrix(new int[][] {{0,0,0},{1,1,0},{1,1,0}}));
	}
	
	int row ;
	int col ;
	int grid[][] ;
	
	class Help{
		int x;
		int y;
		public Help(int x,int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public int shortestPathBinaryMatrix(int[][] grid) {
		Queue<Help> queue = new LinkedList<>();
		int row = grid.length, col = grid[0].length;
		this.row = row;
		this.col = col;
        if(grid[0][0] == 1 || grid[row-1][col-1] == 1) return -1;
        this.grid = grid;
        boolean [][]dp = new boolean[row][col];
        dp[0][0] = true;
        queue.offer(new Help(0,0));
        //开始层次遍历
        int level = 1;
        while(!queue.isEmpty()) {
        	int size = queue.size();
        	while(size > 0) {
        		--size;
        		Help help = queue.poll();
        		if(help.x == row-1 && help.y == col-1) return level;
        		int x = help.x;
        		int y = help.y;
        		if(judge(x-1,y-1)) {
        			if(dp[x-1][y-1]) ;
        			else {
        				dp[x-1][y-1] = true;
        				queue.offer(new Help(x-1,y-1));
        			}
        		}
        		if(judge(x,y-1)) {
        			if(dp[x][y-1]) ;
        			else {
        				dp[x][y-1] = true;
        				queue.offer(new Help(x,y-1));
        			}
        		}
        		if(judge(x+1,y-1)) {
        			if(dp[x+1][y-1]) ;
        			else {
        				dp[x+1][y-1] = true;
        				queue.offer(new Help(x+1,y-1));
        			}
        		}
        		if(judge(x-1,y)) {
        			if(dp[x-1][y]) ;
        			else {
        				dp[x-1][y] = true;
        				queue.offer(new Help(x-1,y));
        			}
        		}
        		if(judge(x+1,y)) {
        			if(dp[x+1][y]) ;
        			else {
        				dp[x+1][y] = true;
        				queue.offer(new Help(x+1,y));
        			}
        		}
        		if(judge(x-1,y+1)) {
        			if(dp[x-1][y+1]) ;
        			else {
        				dp[x-1][y+1] = true;
        				queue.offer(new Help(x-1,y+1));
        			}
        		}
        		if(judge(x,y+1)) {
        			if(dp[x][y+1]) ;
        			else {
        				dp[x][y+1] = true;
        				queue.offer(new Help(x,y+1));
        			}
        		}
        		if(judge(x+1,y+1)) {
        			if(dp[x+1][y+1]) ;
        			else {
        				dp[x+1][y+1] = true;
        				queue.offer(new Help(x+1,y+1));
        			}
        		}
        	}
        	++level;
        }
        return -1;
    }
	
	public boolean judge(int x,int y) {
		if(x<0 || x==row || y<0 || y==col) return false;
		if(grid[x][y] == 1) return false;
		return true;
	}
}
